package 剑指offer;

/**
 * @author: tyy 剑指 Offer
 * 629. K个逆序对数组
 *给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。

逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。

由于答案可能很大，只需要返回 答案 mod 109 + 7 的值。
示例 1:

输入: n = 3, k = 0
输出: 1
解释:
只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。
 * @create: 2021-10-31 17:40
 * @description:
 **/
// 大家别看是困难就躺下了。可以早上看看题，想一想。大脑会在无意间帮你思考的，一天下来说不定哪一刻就有思路了。实在不会就看一点提示再想。绝对不要照抄源码，有思路或者看了题解懂了之后一定要自己写，总结编码技巧和涉及的知识点，再对照别人的学习。祝大家每天都有提升。对了，这个题的提示是：就是个二维的递推加优化。

public class Solution23 {
    private static final int MOD = 1000000007;
    public int kInversePairs(int n, int k) {
        int[][] dp = new int[n][k + 1];
        //dp初始化
        for(int i = 0;i < n;i++){
            dp[i][0] = 1;
        }
        for(int i = 1;i < n;i++){
            for(int j = 1;j <= k;j++){
                long sum = dp[i][j];
                for(int w = 0;w <= i && w <= j;w++){
                    sum += dp[i - 1][j - w];
                }
                dp[i][j] = (int)(sum % MOD);
            }
        }
        return dp[n - 1][k];
    }
    public static void main(String[] args) {
        int timeSeries = 3;
        int duration = 0;
        int number = new Solution23().kInversePairs(timeSeries, duration);
        System.out.println("number = " + number);
        //return "快乐就完了，管那么多干嘛，嗯哼？"


    }
}